Various embodiments of the present invention are related to systems and methods for data processing, and more particularly to systems and methods for data decoding.
Various data processing systems have been developed including storage systems, cellular telephone systems, and radio transmission systems. In such systems data is transferred from a sender to a receiver via some medium. For example, in a storage system, data is sent from a sender (i.e., a write function) to a receiver (i.e., a read function) via a storage medium. As information is stored and transmitted in the form of digital data, errors are introduced that, if not corrected, can corrupt the data and render the information unusable. The effectiveness of any transfer is impacted by any losses in data caused by various factors. Many types of error checking systems have been developed to detect and correct errors in digital data. For example, in perhaps the simplest system, a parity bit can be added to a group of data bits, ensuring that the group of data bits (including the parity bit) has either an even or odd number of ones. When using odd parity, as the data is prepared for storage or transmission, the number of data bits in the group that are set to one are counted, and if there is an even number of ones in the group, the parity bit is set to one to ensure that the group has an odd number of ones. If there is an odd number of ones in the group, the parity bit is set to zero to ensure that the group has an odd number of ones. After the data is retrieved from storage or received from transmission, the parity can again be checked, and if the group has an even parity, at least one error has been introduced in the data. At this simplistic level, some errors can be detected but not corrected.
The parity bit may also be used in error correction systems, including in Low Density Parity Check (LDPC) decoders. An LDPC code is a parity-based code that can be visually represented in a Tanner graph 100 as illustrated in FIG. 1. In an LDPC decoder, multiple parity checks are performed in a number of check nodes 102, 104, 106 and 108 for a group of variable nodes 110, 112, 114, 116, 118, 120, 122, and 124. The connections (or edges) between variable nodes 110-124 and check nodes 102-108 are selected as the LDPC code is designed, balancing the strength of the code against the complexity of the decoder required to execute the LDPC code as data is obtained. The number and placement of parity bits in the group are selected as the LDPC code is designed. Messages are passed between connected variable nodes 110-124 and check nodes 102-108 in an iterative process, passing beliefs about the values that should appear in variable nodes 110-124 to connected check nodes 102-108. Parity checks are performed in the check nodes 102-108 based on the messages and the results are returned to connected variable nodes 110-124 to update the beliefs if necessary. LDPC decoders may be implemented in binary or non-binary fashion. In a binary LDPC decoder, variable nodes 110-124 contain scalar values based on a group of data and parity bits that are retrieved from a storage device, received by a transmission system or obtained in some other way. Messages in the binary LDPC decoders are scalar values transmitted as plain-likelihood probability values or log-likelihood-ratio (LLR) values representing the probability that the sending variable node contains a particular value. In a non-binary LDPC decoder, variable nodes 110-124 contain symbols from a Galois Field, a finite field GF(pk) that contains a finite number of elements, characterized by size pk where p is a prime number and k is a positive integer. Messages in the non-binary LDPC decoders are multi-dimensional vectors, generally either plain-likelihood probability vectors or LLR vectors.
The connections between variable nodes 110-124 and check nodes 102-108 may be presented in matrix form as follows, where columns represent variable nodes, rows represent check nodes, and a random non-zero element a(i,j) from the Galois Field at the intersection of a variable node column and a check node row indicates a connection between that variable node and check node and provides a permutation for messages between that variable node and check node:
  H  =      [                                        a            ⁡                          (                              1                ,                1                            )                                                0                          0                                      a            ⁡                          (                              1                ,                2                            )                                                0                                      a            ⁡                          (                              1                ,                3                            )                                                            a            ⁡                          (                              1                ,                4                            )                                                0                                      0                                      a            ⁡                          (                              2                ,                1                            )                                                0                          0                                      a            ⁡                          (                              2                ,                2                            )                                                0                          0                                      a            ⁡                          (                              2                ,                3                            )                                                                        a            ⁡                          (                              3                ,                1                            )                                                0                                      a            ⁡                          (                              3                ,                2                            )                                                0                                      a            ⁡                          (                              3                ,                3                            )                                                            a            ⁡                          (                              3                ,                4                            )                                                0                                      a            ⁡                          (                              3                ,                5                            )                                                            0                                      a            ⁡                          (                              4                ,                1                            )                                                0                                      a            ⁡                          (                              4                ,                2                            )                                                0                          0                                      a            ⁡                          (                              4                ,                3                            )                                                            a            ⁡                          (                              4                ,                4                            )                                            ]  
By providing multiple check nodes 102-108 for the group of variable nodes 110-124, redundancy in error checking is provided, enabling errors to be corrected as well as detected. Each check node 102-108 performs a parity check on bits or symbols passed as messages from its neighboring (or connected) variable nodes. In the example LDPC code corresponding to the Tanner graph 100 of FIG. 1, check node 102 checks the parity of variable nodes 110, 116, 120 and 122. Values are passed back and forth between connected variable nodes 110-124 and check nodes 102-108 in an iterative process until the LDPC code converges on a value for the group of data and parity bits in the variable nodes 110-124. For example, variable node 110 passes messages to check nodes 102 and 106. Check node 102 passes messages back to variable nodes 110, 116, 120 and 122. The messages between variable nodes 110-124 and check nodes 102-108 are probabilities or beliefs, thus the LDPC decoding algorithm is also referred to as a belief propagation algorithm. Each message from a node represents the probability that a bit or symbol has a certain value based on the current value of the node and on previous messages to the node.
A message from a variable node to any particular neighboring check node is computed using any of a number of algorithms based on the current value of the variable node and the last messages to the variable node from neighboring check nodes, except that the last message from that particular check node is omitted from the calculation to prevent positive feedback. Similarly, a message from a check node to any particular neighboring variable node is computed based on the current value of the check node and the last messages to the check node from neighboring variable nodes, except that the last message from that particular variable node is omitted from the calculation to prevent positive feedback. As local decoding iterations are performed in the system, messages pass back and forth between variable nodes 110-124 and check nodes 102-108, with the values in the nodes 102-124 being adjusted based on the messages that are passed, until the values converge and stop changing or until processing is halted.
Delays may be incurred when check nodes are waiting for messages from variable nodes and when variable nodes are waiting for messages from check nodes. A need therefore remains in the art for data decoders which avoid such delays.